package leetcode_回溯;

/**
 * 单词搜索
 * 算法：回溯
 *
 * @author yezh
 * @date 2024/3/5 13:24
 */
public class _79 {

    public static void main(String[] args) {
        char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        String word = "ABCCED";
        System.out.println(new _79().exist(board, word));
    }

    static int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    String word;
    char[][] board;

    public boolean exist(char[][] _board, String _word) {
        word = _word;
        board = _board;
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (board[i][j] == word.charAt(0) && dfs(0, i, j)) return true;
        return false;
    }

    boolean dfs(int idx, int i, int j) {
        if (idx == word.length() - 1) return true;
        int m = board.length, n = board[0].length;
        char origin = board[i][j];
        board[i][j] = '0';
        for (int[] dir : dirs) {
            int newI = i + dir[0], newJ = j + dir[1];
            if (newI >= 0 && newI < m && newJ >= 0 && newJ < n
                    && board[newI][newJ] != '0'
                    && board[newI][newJ] == word.charAt(idx + 1)
                    && dfs(idx + 1, newI, newJ))
                return true;
        }
        board[i][j] = origin;
        return false;
    }

}
